1. Field of the Invention
The present invention relates to transmitting digital data over a band limited channel by using convolutional coding and multidimensional coded modulation.
2. Background of the Invention
U.S. Pat. No. 4,077,021 to Csajka et al. used 2-dimensional coding to improve the performance of the modem against Gaussian noise. In this scheme the signal constellation was partitioned into 2-dimensional subsets. The minimum distance between the points in each subset was chosen to be larger than the minimum distance in the entire constellation. The indices of the subsets were found to be in one to one correspondence with the outputs of certain convolutional encoders. The input bits to the convolutional encoder were divided into two groups. During each baud (symbol interval), the first group of bits was expanded by the convolutional encoder to create subset selecting bits (coded bits) and the second group of bits, i.e., symbol-selecting bits (uncoded bits) was used to select a member of the subset to be transmitted. Although this coding scheme improved the performance of the system against noise, it also doubled the number of points in the signal constellation making the system more susceptible to other impairments. This is mitigated by the use of a multidimensional code, as described in European Pat. application No. 85300803.5 to Gallager and U.S. Pat. No. 4,581,601.
The multidimensional encoder is usually a (m, m-1) convolutional encoder (i.e., the encoder produces m output bits for m-1 input bits) and when m is even, then m=2n, where n=2, 3, or 4 for 4, 6 or 8 dimensional coded modulation, respectively. Thus, a portion of the encoder output typically comprises a frame of n pairs of subset-selecting bits (i.e., bit pairs), with one of the bit pairs being indexed to a subset of signal points (symbols) of the constellation for each of n bauds. The symbol-selecting bits are used to designate one symbol from each subset of signals (symbols), as with the 2-dimensional convolutional coding. Thus, the encoding process thereby creates within a group interval n 2-dimensional symbols. The symbols within a group interval can be viewed as defining a 2n-dimensional point (symbol) from an available alphabet of 2n-dimensional symbols in 2n-dimensional space.
In a modem using multidimensional coded modulation, to obtain fractional bits per baud, the signal constellation can be divided into inner points and outer points, with one of the uncoded bits indicating for the n 2-dimensional (symbols) whether there are any outer points and at least one uncoded bit to indicate in which of the n bauds the outer point occurs, as shown in the article entitled "Efficient Modulation for Band Limited Channels", G. David Forney et al., IEEE Journal On Selected Areas in Communication, Vol. SAC, 2 September, 1984, pp. 632-645. During each frame the encoder output can be considered as a n point sequence. This n point sequence which will hereafter be referred to as a branch and has two attributes. It can be considered as a sequence of subsets of the constellation, and it can also be considered as a sequence of inner and outer points. In order to minimize the average power output of the modem transmitter and hence to improve the performance of the modem in the presence of noise, it is necessary to send the inner points more often. Thus, usually the allowable sequence of inner and outer points of the encoder form a subset of all possible sequences of inner and outer points. We refer to this subset as subset of sequences as opposed to the subset of signal set.
European patent application No. 86303165.4 teaches, for a multidimensional coded modulation system, a method wherein the most likely sequence of multidimensional signal points to have been sent is determined from the received signal. In this method, the distance is computed between each received constituent signal (with dimensions fewer than that of the multidimensional constellation) and the nearest constituent signal points in the corresponding constituent subsets. The distance between each received multidimensional signal and the nearest multidimensional signal point in each multidimensional subset is determined based on a combination of distances with respect to constituent subsets corresponding to the multidimensional subset. The most likely sequence is determined based on the distances between each received multidimensional signal and the nearest multidimensional signal point in each multidimensional subset.
European patent application No. 86303165.4, on page 20, second column, first paragraph suggest that an improper number of outer points can be determined from the detected bits and that "Then a modification is made on those four groups to render them together valid". However, no method of accomplishing this "modification" is taught.
The present inventors started with the assumption that, for each branch, the decoder must select from among the allowable sequences of inner and outer points, the sequence which is closest in distance to the received sequence. Next, the present inventors considered a brute force approach, which is to compute for each branch the closest sequence of inner and outer points by finding the distance of the received sequence from each of the possible sequences of inner and outer points and comparing these distances to find the sequence of inner and outer points with the least distance. For example, if we have a total of m branches of length n (n baud duration) and k (allowable) sequences of inner and outer points (again of length n), then the brute force approach involves for each branch the following:
1. Compute the distance between the received sequence and an allowable sequence of inner and outer points for that branch.
2. Repeat 1 for every allowable sequence of inner and outer points for the same branch.
3. Compare all the distances and decide which particular allowable sequence of inner and outer points is closest to the received sequence for that branch.
Computations yield for each branch the sequence of inner and outer points nearest to the received sequence, along with the corresponding distance. This branch distance will be referred to as branch metric or branch cost. The m branches can be divided into p subsets (hereafter referred to as cosets) with q members each. The constants with m, p and q are related by the equation: EQU m=pq
The q branches in each coset form parallel branches of the trellis. To compute the cost associated with each transition of the trellis, it is sufficient to use that branch of the coset which has the least cost within that coset. This requires p(q-1) comparisons of costs to come up with p branch costs so the total number of computations needed are:
1. mk distance (cost) computations, and PA1 2. m(k-1)+p(q-1) distance (cost) comparisons. PA1 (i) load accumulator (one instruction), PA1 (ii) ADD accumulator contents to contents of a register (one instruction), and PA1 (iii) store accumulator contents in data memory (one instruction). PA1 (i) store accumulator (one instruction), PA1 (ii) subtract accumulator contents from data memory (one instruction), and PA1 (iii) branch to a certain location if accumulator contents are less than zero (two instructions). Under these conditions the accumulator contents are smaller than the register contents and hence, has to be moved to data memory for further comparison. This in turn requires another instruction so that comparison operation requires at least five instruction cycles. With overhead operations, this algorithm requires maximum of 17776 instruction cycles. Since n=4, this means there are four bauds per frame and hence, the instruction cycles per baud is 4444. Assuming the instruction cycle time is a maximum of 100 nano-seconds, the total time for 4444 instructions is 0.44 milliseconds. If the baud rate is 2,742 Hz, then to perform the algorithm, 1.2 DSPS would be needed making it difficult to implement this algorithm in practice.
In a typical case m is 256, n is 4, k is 5, p is 16 and q is 16. In this case, a total of 1,280 cost computations are needed and 1,264 cost comparisons. The computations can be done with a signal processor (DSP), such as TMS32020. In calculating the number of computations, it has been assumed that for each baud, the square of the distance between the received point and the closet inner point (or any other variable proportional to the square of the distance) has already been computed for each subset. Similarly the square of the distance between the received point and the closest outer point is assumed to have been computed for each baud and each subset. The sequence distance computations can then be done using only additions. For the case of m=256, n=4, k=5, p=16 and q=16, a total of 3,840 additions and 1,264 comparisons have to be made. If this algorithm were to be implemented using commerically available digital signal processors (DSP), such as TMS32025, then most ADD operation requires three instructions:
The above operation requires three instructions. The compare operation requires: